package 题目集.图.最短路;

import java.util.Scanner;

/**
 * https://www.luogu.com.cn/problem/B3647
 */
public class Floyd模板 {
	static int[][] floyd = new int[101][101];
	static int n, m;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			if(floyd[u][v]!=0) {	//有重边的情况
				w=Math.min(w, floyd[u][v]);
			}
			floyd[u][v] = w;
			floyd[v][u] = w;
		}
		floyd();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(floyd[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void floyd() {
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (i == j || floyd[i][k] == 0 || floyd[k][j] == 0) {
						continue;
					}
					if (floyd[i][j] == 0||floyd[i][k] + floyd[k][j]<floyd[i][j]) {
						floyd[i][j] =floyd[i][k] + floyd[k][j];
					}
				}
			}
		}
	}
}
